package algorithm.middle;

import pojo.TreeNode;

import java.util.*;

public class ZigzagLevelOrder103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List res = new ArrayList();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> leftDQ = new LinkedList<>();
        Deque<TreeNode> rightDQ = new LinkedList<>();
        leftDQ.add(root);
        while (!leftDQ.isEmpty() || !rightDQ.isEmpty()) {
            if (!leftDQ.isEmpty()) {
                List<Integer> cur = new ArrayList<>();
                while (!leftDQ.isEmpty()) {
                    TreeNode node = leftDQ.pollFirst();
                    cur.add(node.val);
                    if (node.left != null) {
                        rightDQ.addLast(node.left);
                    }
                    if (node.right != null) {
                        rightDQ.addLast(node.right);
                    }
                }
                res.add(cur);
            } else {
                List<Integer> cur = new ArrayList<>();
                while (!rightDQ.isEmpty()) {
                    TreeNode node = rightDQ.pollLast();
                    cur.add(node.val);
                    if (node.right != null) {
                        leftDQ.addFirst(node.right);
                    }
                    if (node.left != null) {
                        leftDQ.addFirst(node.left);
                    }
                }
                res.add(cur);
            }
        }
        return res;
    }
}
